package com.lry.basic.algorithm.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 简单无向图单源路径问题 指定源点和终点
 */
public class SingleSourceTargetPath {
    private UndirectedGraph graph;
    private int source;//源点
    private int target;//终点
    private int[] dfsPre;//上一个顶点的数组
    private int[] bfsPre;//上一个顶点的数组
    public SingleSourceTargetPath(UndirectedGraph graph, int source, int target){
        graph.validateVertex(source);
        graph.validateVertex(target);
        this.source = source;
        this.target = target;
        this.graph = graph;
        dfsPre = new int[graph.vertexNum()];
        for(int i=0;i<dfsPre.length;i++){
            dfsPre[i] = -1;
        }
        dfs(source,source);

        bfsPre = new int[graph.vertexNum()];
        for(int i=0;i<bfsPre.length;i++){
            bfsPre[i] = -1;
        }
        bfs(source);
    }

    private void bfs(int v){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        while(!queue.isEmpty()){
            int w = queue.poll();
            for(int u:graph.adj(w)){
                if(bfsPre[u]==-1){
                    bfsPre[u] = w;
                    if(u==target){
                        return;
                    }
                    queue.offer(u);
                }
            }
        }
    }

    /**
     * parent-> v 有路径
     * @param v
     * @param parent
     */
    private boolean dfs(int v,int parent){
        dfsPre[v] = parent;
        //走到终点了，返回
        if(v==target){
            return true;
        }
        for(int w:graph.adj(v)) {
            if(dfsPre[w]==-1){
                if(dfs(w,v)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean bfsIsConnected(){
        return bfsPre[target]!=-1;
    }
    public boolean dfsIsConnected(){
        return dfsPre[target]!=-1;
    }

    /**
     * 返回s->t的路径
     * @return
     */
    public Iterable<Integer> dfsPath(){
        List<Integer> list = new ArrayList<>();
        if(!dfsIsConnected()){return list;}
        int cur = target;
        while(cur!=source){
            list.add(0,cur);
            cur = dfsPre[cur];
        }
        list.add(0,source);
        return list;
    }

    public Iterable<Integer> bfsPath(){
        List<Integer> list = new ArrayList<>();
        if(!bfsIsConnected()){return list;}
        int cur = target;
        while(cur!=source){
            list.add(0,cur);
            cur = bfsPre[cur];
        }
        list.add(0,source);
        return list;
    }


    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        SingleSourceTargetPath path = new SingleSourceTargetPath(graph,0,6);
        System.out.println(path.dfsPath());
        System.out.println(path.bfsPath());
    }
}
